#include <vector>
using namespace std;
#include <iostream>


//version 1
class Solution{
private:
    int MergeSortAndGetRerverse_up(vector<int>& tmp, vector<int>& nums, int left, int right){
        if(left >= right) return 0;
        int mid = left + (right - left) / 2;
        //[left, mid] [mid + 1, right]
        int rL = MergeSortAndGetRerverse_up(tmp, nums, left, mid);
        int rR = MergeSortAndGetRerverse_up(tmp, nums, mid + 1, right);

        //回到主逻辑，去找一左一右 + 排序
        //1.在一个数字之前找到所有比它大的数字
        //此时左边是有序的，右边是有序的(升序)
        int ret = rL + rR, i = left;
        int begin1 = left, end1 = mid, begin2 = mid + 1, end2 = right;
        while(begin1 <= end1 && begin2 <= end2){
            if(nums[begin1] <= nums[begin2]) tmp[i++] = nums[begin1++];
            else{
                ret += (end1 - begin1 + 1);
                tmp[i++] = nums[begin2++];
            }
        }
        while(begin1 <= end1) tmp[i++] = nums[begin1++];
        while(begin2 <= end2) tmp[i++] = nums[begin2++];

        //排好序的数组(局部)放在tmp上，给他放回去
        for(int j = left; j < i; ++j) nums[j] = tmp[j];
        return ret;
    }

    int MergeSortAndGetRerverse_down(vector<int>& tmp, vector<int>& nums, int left, int right){
        if(left >= right) return 0;
        int mid = left + (right - left) / 2;
        //[left, mid] [mid + 1, right]
        int rL = MergeSortAndGetRerverse_down(tmp, nums, left, mid);
        int rR = MergeSortAndGetRerverse_down(tmp, nums, mid + 1, right);
        

        //回到主逻辑，我们这一次是走的降序！（只需要改一下合并数组的逻辑）
        //->就找一个数字后比它小的数字
        int ret = rL + rR, i = left;
        int begin1 = left, end1 = mid, begin2 = mid + 1, end2 = right;
        while(begin1 <= end1 && begin2 <= end2){
            if(nums[begin1] > nums[begin2]) {
                ret += (end2 - begin2 + 1);
                tmp[i++] = nums[begin1++];
            }
            else tmp[i++] = nums[begin2++];
        }
        while(begin1 <= end1) tmp[i++] = nums[begin1++];
        while(begin2 <= end2) tmp[i++] = nums[begin2++];

        for(int j = left; j < i; ++j) nums[j] = tmp[j];
        return ret;
    }
public:
    int reversePairs(vector<int>& nums){
        vector<int> tmp(nums.size());
        //return MergeSortAndGetRerverse_up(tmp, nums, 0, nums.size() - 1);
        return MergeSortAndGetRerverse_down(tmp, nums, 0, nums.size() - 1);
    }
};

std::vector<int> getArrayWith200Inversions() {
    return std::vector<int>{
        16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, -1, -2, -3, -4, -5         
        // 16个逆序元素 (120逆序对)
                             // 5个更小的元素 (增加80逆序对)
        // 总计: 120 + 80 = 200逆序对
    };
}

int main(){
    vector<int> v = getArrayWith200Inversions();
    vector<int> v1 = {7,5,6,4};
    cout << Solution().reversePairs(v1) << endl;
}